#include "stdio.h"
#include "stdlib.h"
#include "queue"
#include "stack"

using namespace std;

typedef struct node
{
    int data;
    struct node *lchild;
    struct node *rchild;
}BTreeNode;

//初始化一个二叉树节点
BTreeNode *nodeInit(int n)
{
    BTreeNode *node;
    node=(BTreeNode *)malloc(sizeof(BTreeNode));
    node->data=n;
    node->lchild=NULL;
    node->rchild=NULL;
}

//先序递归遍历二叉树
void preOrder(BTreeNode *root)
{
    if(root!=NULL)
    {
        printf("%d ",root->data);
        preOrder(root->lchild);
        preOrder(root->rchild);
    }
}

//先序遍历二叉树非递归算法
void preOrderNonRecur(BTreeNode *root)
{
    stack<BTreeNode *> s;
    BTreeNode *p;

    if(root!=NULL)
    {
        s.push(root);
        while(!s.empty())
        {
            p=s.top();
            printf("%d ",p->data);
            s.pop();
            if(p->rchild!=NULL)
                s.push(p->rchild);
            if(p->lchild!=NULL)
                s.push(p->lchild);
        }
        printf("\n");
    }
}

//中序递归遍历二叉树
void inOrder(BTreeNode *root)
{
    if(root!=NULL)
    {
        inOrder(root->lchild);
        printf("%d ",root->data);
        inOrder(root->rchild);
    }
}

//中序遍历二叉树非递归算法
void inOrderNonRecur(BTreeNode *root)
{
    stack<BTreeNode *> s;
    BTreeNode *p;

    p=root;
    while(p!=NULL||!s.empty())
    {
        while(p!=NULL)
        {
            s.push(p);
            p=p->lchild;
        }
        if(!s.empty())
        {
            p=s.top();
            printf("%d ",p->data);
            s.pop();
            p=p->rchild;
        }
    }
    printf("\n");
}

//后序递归遍历二叉树
void postOrder(BTreeNode *root)
{
    if(root!=NULL)
    {
        postOrder(root->lchild);
        postOrder(root->rchild);
        printf("%d ",root->data);
    }
}

//后序非递归遍历二叉树
void postOrderNonRecur(BTreeNode *root)
{
    stack<BTreeNode *> s;
    BTreeNode *pre,*p;

    pre=NULL;
    if(root!=NULL)
    {
        s.push(root);
        while(!s.empty())
        {
            p=s.top();
            if(p->lchild==NULL&&p->rchild==NULL||
               (pre!=NULL&&(pre==p->lchild||pre==p->rchild)))
               //如果栈顶节点没有子节点或者子节点被访问过，则访问子节点
            {
                printf("%d ",p->data);
                pre=p;
                s.pop();
            }
            else
            {
                if(p->rchild!=NULL)
                    s.push(p->rchild);
                if(p->lchild!=NULL)
                    s.push(p->lchild);
            }
        }
        printf("\n");
    }
}

//层次遍历二叉树
void levelOrder(BTreeNode *root)
{
    queue<BTreeNode *> qu;
    BTreeNode *p;

    if(root!=NULL)
    {
        qu.push(root);
        while(!qu.empty())
        {
            p=qu.front();
            printf("%d ",p->data);
            if(p->lchild!=NULL)
                qu.push(p->lchild);
            if(p->rchild!=NULL)
                qu.push(p->rchild);
            qu.pop();
        }
    }
}

//在二叉树中查找值为x的节点，返回节点的指针
BTreeNode *findNode(BTreeNode *root,int x)
{
    BTreeNode *p;
    if(root==NULL)
        return NULL;
    if(root->data==x)
        return root;
    p=findNode(root->lchild,x);
    if(p!=NULL)
        return p;
    else
        return findNode(root->rchild,x);
}

//求二叉树的高度
int binaryHeight(BTreeNode *root)
{
    int h1,h2;
    if(root==NULL)
        return 0;
    h1=binaryHeight(root->lchild);
    h2=binaryHeight(root->rchild);
    if(h1>h2)
        return h1+1;
    else
        return h2+1;
}

//括号表示法输入二叉树
void dispBinTree(BTreeNode *root)
{
    if(root!=NULL)
    {
        printf("%d ",root->data);
        if(root->lchild!=NULL||root->rchild!=NULL)
        {
            printf("(");
            dispBinTree(root->lchild);
            if(root->rchild!=NULL)
                printf(",");
            dispBinTree(root->rchild);
            printf(")");
        }
    }
}

//计算二叉树节点个数
int nodes(BTreeNode *root)
{
    if(root==NULL)
        return 0;
    else
        return 1+nodes(root->lchild)+nodes(root->rchild);
}

//计算二叉树叶子节点个数
int leafNodes(BTreeNode *root)
{
    if(root==NULL)
        return 0;
    else if(root->lchild==NULL&&root->rchild==NULL)
        return 1;
    else
        return leafNodes(root->lchild)+leafNodes(root->rchild);
}

//计算二叉树非叶子节点个数
int notLeafNodes(BTreeNode *root)
{
    if(root==NULL)
        return 0;
    else if(root->lchild==NULL&&root->rchild==NULL)
        return 0;
    else
        return 1+leafNodes(root->lchild)+leafNodes(root->rchild);
}

//查找二叉树中值为x的节点的层次
int findNodeLevel(BTreeNode *root,int h,int x)
{
    int hl;

    if(root==NULL)
        return 0;
    if(root->data==x)
        return h;
    hl=findNodeLevel(root->lchild,h+1,x);
    if(hl!=0)
        return hl;
    else
        return findNodeLevel(root->rchild,h+1,x);
}

//统计二叉树中第k层节点的个数n
void kLevelNodes(BTreeNode *root,int h,int k,int &n)
{
    if(root==NULL)
        return;
    else
    {
        if(h==k)
            n++;
        else if(h<k)
        {
            kLevelNodes(root->lchild,h+1,k,n);
            kLevelNodes(root->rchild,h+1,k,n);
        }
    }
}

int main()
{
    BTreeNode *root=nodeInit(1);
    BTreeNode *p;
    int height;

    root->lchild=nodeInit(2);
    root->rchild=nodeInit(3);
    root->lchild->lchild=nodeInit(4);
    root->rchild->lchild=nodeInit(5);
    root->rchild->rchild=nodeInit(6);
    root->lchild->lchild->rchild=nodeInit(7);

    printf("--------------------------------\n");
    printf("先序递归遍历二叉树:\n");
    preOrder(root);
    printf("\n\n");

    printf("先序非递归遍历二叉树:\n");
    preOrderNonRecur(root);
    printf("\n");

    printf("--------------------------------\n");
    printf("中序递归遍历二叉树:\n");
    inOrder(root);
    printf("\n\n");

    printf("中序非递归遍历二叉树:\n");
    inOrderNonRecur(root);
    printf("\n");

    printf("--------------------------------\n");
    printf("后序递归遍历二叉树:\n");
    postOrder(root);
    printf("\n\n");

    printf("后序非递归遍历二叉树:\n");
    postOrderNonRecur(root);
    printf("\n");

    printf("--------------------------------\n");
    printf("层次遍历二叉树:\n");
    levelOrder(root);
    printf("\n\n");

    printf("--------------------------------\n");
    if(p=findNode(root,7))
        printf("元素%d查找成功\n\n",p->data);
    else
        printf("元素7查找失败\n\n");

    if(p=findNode(root,8))
        printf("元素%d查找成功\n\n",p->data);
    else
        printf("元素8查找失败\n\n");

    printf("--------------------------------\n");
    height=binaryHeight(root);
    printf("二叉树的高度为%d\n",height);

    printf("--------------------------------\n");
    printf("\n括号表示法输出二叉树:");
    dispBinTree(root);
    printf("\n");

    printf("--------------------------------\n");
    printf("\n二叉树节点数为:%d\n\n",nodes(root));

    printf("二叉树叶子节点数为:%d\n\n",leafNodes(root));

    printf("二叉树非叶子节点数为:%d\n\n",notLeafNodes(root));


    printf("--------------------------------\n");
    printf("元素%d在二叉树中的层次为:%d\n\n",7,findNodeLevel(root,1,7));

    printf("元素%d在二叉树中的层次为:%d\n\n",8,findNodeLevel(root,1,8));

    int n=0;
    kLevelNodes(root,1,3,n);
    printf("二叉树中第%d层节点的个数:%d\n",3,n);

    return 0;
}
